package j_UnionFind;

// 我们的第四版Union-Find
/**			问题：基于size优化 or 基于rank优化？？
rank 的优化只是“理论”上比 size 的优化更优，因为“理论”上可以让整个并查集的高度更低。
但对于实际情况，有可能因为测试用例本身不会形成那么高的树，从而使得优化本身更费时间（因为需要更多的判断和操作）。
这就好比，归并排序理论上比插入排序更快，但是，如果数组本身有序，其实插入排序更快；如果数据量比较小，也很有可能插入排序更快。
	**所有的优化都不能保证在所有的情况下都更优。关键是：
	  		1）对于极端情况，优化的效果更好；
	  		2）对于平均情况，优化的效果不差。
	  		
	  个人总结：基于size和基于rank其实各有千秋。因为查找是从某个节点出发一直到root为止的，基于size是因为：被同化的时候 被同化的树的所有节点的查询次数+1；
	  			但另一个方面：如果基于rank，会尽可能避免合并后树的最大高度增加；因为基于size有可能把rank高的合并到rank低的，从而使合并后的rank变成 原rank_max+1，而基于rank会避免这种情况，rank只会变成 原rank_max；
 *
 *Main函数测试结果：
 *基于size or 基于rank。。根本拉不开差距
 *但经典的并查集实现里使用的是rank优化，可能基于size有哪些极端场景会崩？TODO:
 *
 *最关键的优化是 rank/size 的优化，
 *路径压缩在百万规模时 只会拖后腿，因为数据规模小，深度并不大，导致额外的操作反而更费时间； 
 *BUT，恰恰数据规模并不大时，本身也就不太耗时间，所以这时候拖的后腿是完完全全可忽略的，当数据规模大的时候优势还是很大的；
 * 
 */
public class UnionFind4_rank implements UF {

    private int[] rank;   // rank[i]表示以i为根的集合所表示的树的层数
    private int[] parent; // parent[i]表示第i个元素所指向的父节点

    // 构造函数
    public UnionFind4_rank(int size){

        rank = new int[size];	//这里的实现是	一个树合并到别的树后，原来的rank值不取消；如果想知道森林里有多少树("极大连通分量")，可以在合并时的维护rank时，把被同化的树置为默认值，也就是只对各个root进行维护；
        parent = new int[size];

        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){
        return parent.length;
    }

    // 查找过程, 查找元素p所对应的集合编号（所在树的root）
    // O(h)复杂度, h为树的高度
    private int find(int p){	
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        //这里就体现了，根节点指向自己的好处，其实根节点指向任何无意义索引节点都可以标明其为root，但指向自己话，还可以说明第二层节点的爷爷节点，曾爷爷节点..都还是root；//所以这里不会出现索引越界的情况；我先判断的索引合法，结果判断完还得担心索引合不合法，这样就很乱，所以对于像这样 root指针有多种选择的这种情况，要学会换角度选择；
        while(p != parent[p])             //用根节点表示一个连通集合
            p = parent[p];
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度, h为树的高度
    @Override
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    @Override
    public void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        // 根据两个元素所在树的rank不同判断合并方向
        // 将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if(rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // 此时维护rank值，不取消被同化树的rank值，即每个节点都有rank值；
        }
    }
}
